package com.ljy.my_study.lintcode.全排列;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/** 
* @author James
* @date 2018年9月21日 
*/
public class TestMain {
//	描述
//	给定一个数字列表，返回其所有可能的排列。
//
//	你可以假设没有重复数字。
//
//	您在真实的面试中是否遇到过这个题？  
//	样例
//	给出一个列表[1,2,3]，其全排列为：
//
//	[
//	  [1,2,3],
//	  [1,3,2],
//	  [2,1,3],
//	  [2,3,1],
//	  [3,1,2],
//	  [3,2,1]
//	]
//	挑战
//	使用递归和非递归分别解决。
	public static void main(String[] args) {
		TestMain testMain=new TestMain();
		int[] nums= {5,4,6,2};
		testMain.println(testMain.permute(nums));
	}
	
	private void println(List<List<Integer>> listList) {
		for(List<Integer> list:listList) {
			System.out.println(list.toString());
		}
	}
	
	public List<List<Integer>> permute(int[] nums) {
		if(nums.length==0) {
			List<List<Integer>> listList=new ArrayList<>();
			listList.add(new ArrayList<>());
			return listList;
		}
		List<List<Integer>> twoDimensionList=new ArrayList<>();
		int n=0;
		for(int i=0;i<nums.length;i++) {
			List<Integer> list=changeArrayToList(nums);
			if(n!=i) {
				Integer a=list.get(n);
				Integer b=list.get(i);
				list.set(n, b);
				list.set(i, a);
			}
			twoDimensionList.add(list);
		}
		List<List<Integer>> listList=new ArrayList<>();
		int count=1;
		while(count<nums.length-1) {
			for(int i=0;i<twoDimensionList.size();i++) {
				for(int j=count;j<nums.length;j++) {
					List<Integer> list=new ArrayList<>(twoDimensionList.get(i));
					if(j!=count) {
						Integer a=list.get(count);
						Integer b=list.get(j);
						list.set(count, b);
						list.set(j, a);
						listList.add(list);
					}
				}
			}
			twoDimensionList.addAll(listList);
			listList.clear();
			count++;
		}
		return twoDimensionList;
	}
	
	private List<Integer> changeArrayToList(int[] nums) {
		List<Integer> list=new ArrayList<>();
		for(int i=0;i<nums.length;i++) {
			list.add(nums[i]);
		}
		return list;
	}
}
